Perfect and separating Hash families: new bounds via the algorithmic cluster expansion local lemma

摘要

We present new lower bounds for the size of perfect and separating hashfamilies ensuring their existence. Such new bounds are based on the algorithmicCluster expansion improved version of the Lov\'asz Local Lemma, which alsoimplies that the Moser-Tardos algorithm finds such hash families in polynomialtime.